package BinaryTree;//根据一棵树的中序遍历与后序遍历构造二叉树。
//
// 注意: 
//你可以假设树中没有重复的元素。 
//
// 例如，给出 
//
// 中序遍历 inorder = [9,3,15,20,7]
//后序遍历 postorder = [9,15,7,20,3] 
//
// 返回如下的二叉树： 
//
//     3
//   / \
//  9  20
//    /  \
//   15   7
// 
// Related Topics 树 数组 哈希表 分治 二叉树 👍 616 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class buildTreeI {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        /**
         * 根据遍历特性 可以看出 根节点的值在后续遍历的最后
         * 且根节点确定，那么在中序遍历中即可确定左右子树，
         * 中序遍历根节点的左侧即左子树，右侧即右子树
         * */
        int lenI = inorder.length;
        int lenP = postorder.length;
        if(lenI==0 || lenP==0){
            return null;
        }
        return build(postorder,0,lenP-1,
                inorder,0,lenI-1);
    }
    private TreeNode build(int[] postorder, int postLeft, int postRight,
                           int[] inorder, int inLeft, int inRight){

        /**
         * 这里的四个下标采取的是闭包原则，不是左闭右开
         * */
        // 递归终止条件
        if (inLeft > inRight || postLeft > postRight){
            return null;
        }
        //后续遍历的最右侧是根节点, 获取该节点值，并建立节点
        int val = postorder[postRight];
        TreeNode root = new TreeNode(val);
        //从中序遍历中找到该节点所在的下标，左边为左子树部分，右边为右子树部分
        int index = 0;
        for (index = inLeft; index <= inRight ; index++) {
            if(inorder[index] == val){
                break;
            }
        }
        //找到在中序遍历中的位置，就可以查出左右子树的大小，根据该大小也可以把其在后序遍历中分开
        int leftNum = index - inLeft;
        int rightNum = inRight - index;
        root.left = build(postorder, postLeft, postLeft+leftNum-1,
                inorder, inLeft, index-1);
        root.right = build(postorder, postRight-rightNum,postRight-1,
                inorder, index+1,inRight);
        return root;

    }
}
//leetcode submit region end(Prohibit modification and deletion)
